package leetcode_41_60;

import java.util.ArrayList;
import java.util.List;

public class multiply_43 {
    /**
     * 注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
     * 并且位数最多能达到200位
     * 思路是模拟乘法，转化为加法运算
     * 最后逐位计算拼接
     *
     * 太慢了
     * 16ms
     * @param num1
     * @param num2
     * @return
     */
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0"))
            return "0";
        StringBuilder ans=new StringBuilder();
        List<List<Integer>> lists  =new ArrayList<>();   //模拟乘法每一步的结果集
        int carry=0;      //进位
        for(int i=num1.length()-1;i>=0;i--){    //模拟乘法，外层遍历的是下边的乘数num1的每一位
                                                                        //      9 9
                                                                        // ×  9 9
                                                                      //     8 9 1
                                                                      //  8 9 1 0
                                                                      //  9 8 0 1
            int a=num1.charAt(i)-'0';
            //根据每一位对结果末尾加对应数量的0
            List<Integer> part=new ArrayList<>();
            for(int j=i;j<num1.length()-1;j++)
                part.add(0);
            for(int t=num2.length()-1;t>=0;t--){ //内层遍历的是下边的乘数的每一位
                int b=num2.charAt(t)-'0';
                int result=a*b+carry;              //该位的计算结果
                part.add( result %10 );    //该位的数字
                carry=result/10;               //计算进位数
            }
            if(carry!=0){                 //到最后一位时，如果还有进位  如上边例子中8 9 1 中的 8
                part.add(carry);
                carry=0;
            }
            lists.add(part);
        }
        carry=0;
        for(int i=0;i<lists.get(lists.size()-1).size();i++){         //最后一个数组的位数最大,以它的大小遍历
            // 集合中的数组是倒过来的 43210 存储的是 12340
            int sum=0;     //所有数在这一位的和
            for(int t=0;t<lists.size();t++){
                int size = lists.get(t).size(); //此时数字的位数
                if(i>size-1)  //位数不够参与运算直接跳过
                    continue;
                sum+=lists.get(t).get(i);
            }
            ans.append( (sum+carry ) %10 );    //该位的数字
            carry=(sum+carry )/10;               //计算进位数
        }
        if(carry!=0){
            ans.append(carry);  //到最后一位时，如果还有进位
        }
        return ans.reverse().toString();
    }

    /**
     * 思路类似的优化版
     * 即计算出num1和num2的所有需要相乘的两个数字的结果直接加到结果对应的位置
     * 如123的3 第三位和45的第二位相乘得15，个位直接加到3+2位，产生的进位加到  3+2 -1 位
     * 2ms
     */
    public String multiply2(String num1, String num2) {
        /*
         *                1 2 3
         *  ×               4 5
         *                    1 5
         *                 1 0
         *              0 5
         *                 1 2
         *              0 8
         *           0 4
         *           0 5 5 3 5   //结果直接设为3+2 位
         */
        if (num1.equals("0") || num2.equals("0"))
            return "0";
        StringBuilder ans=new StringBuilder();
        int[] res = new int[num1.length() + num2.length()]; //结果直接设为3+2 位
        int carry=0;      //进位
        for(int i=num1.length()-1;i>=0;i--){    //模拟乘法，外层遍历的是下边的乘数num1的每一位
            int a=num1.charAt(i)-'0';
            for(int t=num2.length()-1;t>=0;t--){   //内层遍历的是下边的乘数的每一位
                int b=num2.charAt(t)-'0';
                //计算num1的第 i 位和num2的第 t 位 相乘的结果 个位加到结果的第  i + t + 1位，产生的进位加到  i + t 位
                int sum = (res[i + t + 1] + a * b); //当前位的和
                res[i + t + 1] = sum % 10;  //当前位实际数字
                res[i + t] += sum / 10;        //提前给前一位加上进位数
            }
        }
        for (int i = 0; i < res.length; i++) {
            if (i == 0 && res[i] == 0) continue;
            ans.append(res[i]);
        }
        return ans.toString();
    }

    /**
     * 也可以用一种叫做快速傅立叶变换（Fast Fourier Transform，FFT）的方法来加速卷积的计算，
     * 使得时间复杂度降低到 O(clog⁡c)O(c \log c)O(clogc)
     * 这里 ccc 是不小于 n+mn + mn+m 的最小的 222 的整数幂
     *
     * 我不会
     */
}
